1. Field of the Invention
The present invention relates to a method of making an integrated circuit having data path modules displaying a regularity or repetitiveness in the integrated circuit, the method including floor planning the integrated circuit according to an iterative process having as inputs a first approximation of electrical pin ordering and number of slices (nodes with branches) for the integrated circuit, and including the extraction of similarity information concerning the locations and associations of the data path circuit cells of the integrated circuit. The resulting floor plan for the integrated circuit minimizes the number of open nets in the interconnections of the integrated circuit while also greatly reducing the amount of computer time required to complete the floor plan.
2. Related Technology
As application-specific integrated circuits (ASIC's) become larger, approaching and exceeding 200,000 cells, the burden of laying out or floor planning these integrated circuits becomes extremely great. Trying to floor plan such integrated circuits without the use of a hierarchy is extremely difficult and is not advisable for two reasons. First, the storage (memory) and computing burden grow non-linearly with the increase of the design size. Secondly, integrated circuits which have been laid out with a hierarchical approach display improved performance. Accordingly, a building-block type approach to floor planning complex integrated circuits is favored, which includes a top-down and bottom-up approach. The top-down aspect of floor planning includes a global assignment of electrical connection pins and feed-through connectors, while the bottom-up aspect includes laying out modules separately at a reasonable size after partitioning. Finally, a routing of the macro cells is applied to finish the layout.
In the computer-aided design (CAD) ASIC industry, there are several existing approaches to the layout of circuit modules, and which extend in some case to the lay out of entire integrated circuits. Min-cut, force directed techniques, simulated annealing, and quadratic programming algorithms such as "Proud", and "Gordian", have been advanced. Some of these focus on the connections necessary within the integrated circuit between the cells of the circuit. Some are addressed to a single hierarchical level of the integrated circuit, and optimize only that level of the circuit. Most generally, the optimized level is the top level of the circuit. Some of these layout planners have as an advantage the minimizing of the interconnecting wire length in the circuit on a global basis. Others equalize the interconnection wire lengths at the expense of greater global wire lengths in order to level connection times (prevent timing discrepancies) within the circuit. However, these conventional approaches focus on general designs of integrated circuits, and are based on connectivity or electrical interconnections between cells and other circuit elements within the integrated circuit.
However, some integrated circuits include data path modules and are more or less rich in these data path modules. Data path modules have a two-dimensional repetitive structure which lends a regularity to an integrated circuit including such data path modules. A few algorithms have been proposed for placing data path modules on integrated circuits taking advantage of some aspect of the regularity of the circuit structure. W. K. Luk and A. A. Dean, in their paper entitled, "Multi-stack Optimization for Data-Path Chip (Microprocessor) Layout", IEEE Proc. of Design Automation Conf., 1989, pp. 110-115, proposed a multi-stack optimization for laying out or floor planning integrated circuit chips including data path modules. This method employed a modification of the min-cut algorithm to partition cells of the circuit structure into stacks while maintaining approximately equal heights for the several stacks. Cells are then swapped or exchanged among the several stacks to improve the overall placement of cells in the circuit floor plan.
An aspect of extraction of regularity information from the functional design of an integrated circuit was proposed by M. Hirsch and D. Siewiorek, in their paper entitled, "Automatically Extracting Structure from a Logical Design", IEEE Proc. of Int. Conf. on CAD, 1988, pp. 456-459. However, the floor plan of the integrated circuit used only pre-placed cells as seeds around which the remainder of the circuit was grown using connectivity information.
More particularly, data path modules have a repetitiveness to their structure as presented in the total context of an integrated circuit. The data path modules have a two-dimensional nature to their circuit structure, and large fan-out nets of control connections to other cells of the integrated circuit. On these fan-out control connection nets, the cells are topographically and logically the same. In other words, in such an integrated circuit, the fan-out control nets with data path modules effectively repeat a slice structure of the circuit. A repetitive node with repetitive and duplicated branches is seen within the integrated circuit as a result.
The mere idea of extracting cells on such control nets into a macro was proposed by G. Odawanre, T. Haraide, and O. Nishina, in their paper entitled "Partitioning and Placement Technique for CMOS Gate Array", presented to the IEEE Transactions, May 1987, vol CAD6, No. 3, pp 335-363. However, the particulars of the use of such a macro was not developed as herein set forth.